import sys
sys.path.append("/Users/ender/Code_repo/rosalind-brush-questions")
sys.setrecursionlimit(999999) # 默认的递归深度不能完成序列的搜索
from utils import read_fasta


"""
递归遍历的时间复杂度约为 O(2^n * 2^m) = O(2^(m + n))
思路如下：
- 如果 s1[-1] 与 s2[-1] 相等，LCS(s1, s2) = LCS(s1[:-1], s2[:-1]) + 1
- 如果 s1[-1] 与 s2[-1] 不相等，LCS(s1, s2) = max(LCS(s1[:-1], s2), LCS(s1, s2[:-1]))
- 边界条件：当 s1 或 s2 为空时，LCS(s1, s2) = 0
实现函数：lcs

对于长序列计算时间过长，因为直接递归会重复计算很多次中间结果，如果在递归的过程把计算过的中间结果用 dict 保存下来，
下次用到再取出来会明显增加程序的运行效率。
实现函数：lcs2
"""

def lcs(s1, s2):
    if (len(s1) == 0) or (len(s2) == 0):
        return "", 0
    
    if s1[-1] == s2[-1]:
        last_cs, last_lcs = lcs(s1[:-1], s2[:-1])
        return last_cs + s1[-1], last_lcs + 1
    else:
        last_cs1, last_lcs1 = lcs(s1[:-1], s2)
        last_cs2, last_lcs2 = lcs(s1, s2[:-1])
        if last_lcs1 > last_lcs2:
            return last_cs1, last_lcs1
        else:
            return last_cs2, last_lcs2

temp_dict = {}
def lcs2(s1, s2):
    if (len(s1) == 0) or (len(s2) == 0):
        if (s1, s2) in temp_dict:
            return temp_dict[(s1, s2)]
        else:
            temp_dict[(s1, s2)] = ("", 0)
            return ("", 0)
    
    if s1[-1] == s2[-1]:
        if (s1[:-1], s2[:-1]) in temp_dict:
            last_cs, last_lcs = temp_dict[(s1[:-1], s2[:-1])]
        else:
            temp_dict[(s1[:-1], s2[:-1])] = lcs2(s1[:-1], s2[:-1])
            last_cs, last_lcs = lcs2(s1[:-1], s2[:-1])

        return last_cs + s1[-1], last_lcs + 1
    else:
        if (s1[:-1], s2) in temp_dict:
            last_cs1, last_lcs1 = temp_dict[(s1[:-1], s2)]
        else:
            temp_dict[(s1[:-1], s2)] = lcs2(s1[:-1], s2)
            last_cs1, last_lcs1 = lcs2(s1[:-1], s2)
        
        if (s1, s2[:-1]) in temp_dict:
            last_cs2, last_lcs2 = temp_dict[(s1, s2[:-1])]
        else:
            temp_dict[(s1, s2[:-1])] = lcs2(s1, s2[:-1])
            last_cs2, last_lcs2 = lcs2(s1, s2[:-1])
        if last_lcs1 > last_lcs2:
            return last_cs1, last_lcs1
        else:
            return last_cs2, last_lcs2
    # if (s1, s2) not in temp_dict:



# fasta = read_fasta("./test.txt")
# fasta = read_fasta("./15_FindingSharedSplicedMotif/test.txt")
fasta = read_fasta("./rosalind_lcsq (2).txt")
s1, s2 = [v for v in fasta.values()]

print(lcs2(s1, s2))

